package com.lft.ten_commonly_used_algorithms10.knights_tour_problem;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 马踏棋盘（骑士周游）
 */
public class KnightsTourProblemDemo {
	public static void main(String[] args) {
		ChessBoard chessBoard = new ChessBoard(8, 8);
		int i = 0;
		int j = 5;
		System.out.println("从 " + i + " 行 " + j + " 列出发的路线为：");
		
		long startTime = System.currentTimeMillis();
		chessBoard.traversalChessBoard(i, j, 1);
		long endTime = System.currentTimeMillis();
		System.out.println("耗时：" + (endTime - startTime) + " 毫秒");
		for (int[] ints : chessBoard.chessBoard) {
			System.out.println(Arrays.toString(ints));
		}
	}
}

/**
 * 棋盘类
 */
class ChessBoard {
	/**
	 * 表示棋盘
	 */
	int[][] chessBoard;
	/**
	 * 棋盘的行数
	 */
	int row;
	/**
	 * 棋盘的列数
	 */
	int col;
	/**
	 * 标记棋盘的位置是否被访问过。
	 */
	boolean[][] visited;
	
	/**
	 * 标记棋盘是否全部被访问过。
	 */
	boolean finished;
	
	/**
	 * 构造器
	 * @param row 行数
	 * @param col 列数
	 */
	public ChessBoard(int row, int col) {
		this.row = row;
		this.col = col;
		this.chessBoard = new int[row][col];
		this.visited = new boolean[row][col];
		this.finished = false;
	}
	
	/**
	 * 根据当前位置（Point 对象），计算马还能走哪些位置（Point），并放入到一个集合中（ArrayList），最多有 8 个位置。
	 * @param currentPoint
	 * @return
	 */
	public ArrayList<Point> nextPoint(Point currentPoint) {
		// 创建一个 ArrayList<Point>
		ArrayList<Point> result = new ArrayList<>();
		// 创建一个 Point
		Point point = new Point();
		// 左移1，上移2
		if ((point.x = currentPoint.x - 1) >= 0 && (point.y = currentPoint.y - 2) >= 0) {
			result.add(new Point(point));
		}
		// 左移1，下移2
		if ((point.x = currentPoint.x - 1) >= 0 && (point.y = currentPoint.y + 2) < row) {
			result.add(new Point(point));
		}
		// 左移2，上移1
		if ((point.x = currentPoint.x - 2) >= 0 && (point.y = currentPoint.y - 1) >= 0) {
			result.add(new Point(point));
		}
		// 左移2，下移1
		if ((point.x = currentPoint.x - 2) >= 0 && (point.y = currentPoint.y + 1) < row) {
			result.add(new Point(point));
		}
		// 右移1，上移2
		if ((point.x = currentPoint.x + 1) < col && (point.y = currentPoint.y - 2) >= 0) {
			result.add(new Point(point));
		}
		// 右移1，下移2
		if ((point.x = currentPoint.x + 1) < col && (point.y = currentPoint.y + 2) < row) {
			result.add(new Point(point));
		}
		// 右移2，上移1
		if ((point.x = currentPoint.x + 2) < col && (point.y = currentPoint.y - 1) >= 0) {
			result.add(new Point(point));
		}
		// 右移2，下移1
		if ((point.x = currentPoint.x + 2) < col && (point.y = currentPoint.y + 1) < row) {
			result.add(new Point(point));
		}
		return result;
	}
	
	/**
	 * 骑士周游问题的算法方法
	 * @param startRow   马儿当前位置行
	 * @param startCol   马儿当前位置列
	 * @param chessBoard 棋盘
	 * @param step       马儿当前走第几步（初始位置是1）
	 */
	public void traversalChessBoard(int startRow, int startCol, int step) {
		// 在棋盘上填写位置序号
		this.chessBoard[startRow][startCol] = step;
		// 设置当前位置已经访问
		this.visited[startRow][startCol] = true;
		// 获取当前位置可以走的下一个位置的集合。
		ArrayList<Point> list = nextPoint(new Point(startRow, startCol));
		// 【优化】对 list 中的元素进行非递减排序
		sort(list);
		// 不空。
		while (!list.isEmpty()) {
			// 取出一个位置
			Point point = list.remove(0);
			// 如果当前没有被访问过
			if (!this.visited[point.x][point.y]) {
				// 递归回溯遍历，频数+1
				traversalChessBoard(point.x, point.y, step + 1);
			}
		}
		// 判断走了多少步了
		// 步数小于棋盘格子。并且 finished 棋盘没有全部走完。
		if (step < this.row * this.col && !this.finished) {
			this.chessBoard[startRow][startCol] = 0;
			// 设置当前位置已经访问
			this.visited[startRow][startCol] = false;
		} else {
			// 说明 棋盘遍历完了。
			this.finished = true;
		}
	}
	
	/**
	 * 排序
	 * @param list
	 */
	public void sort(ArrayList<Point> list) {
		list.sort(new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				return nextPoint(o1).size() - nextPoint(o2).size();
			}
		});
	}
}